package com.sise.Linked;

/**
 *      92. 反转链表 II
 *
 *      给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。
 *      请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
 *
 *      输入：head = [1,2,3,4,5], left = 2, right = 4
 *      输出：[1,4,3,2,5]
 *
 *      题解：双指针、头插法
 *      https://leetcode-cn.com/problems/reverse-linked-list-ii/solution/java-shuang-zhi-zhen-tou-cha-fa-by-mu-yi-cheng-zho/
 *
 */
public class _92_reverseBetween {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        // 设置哑元节点，使其指向 head
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;

        ListNode pre = dummyHead;
        ListNode point = dummyHead.next;

        // 将指针移动到相对应的位置
        for (int step = 0; step < left; step++){
            pre = pre.next;
            point = point.next;
        }

        // 这里循环后，point 仍是 2，2 的下一个数字为 4，可以将其循环头插入法，变为[1,4,3,2,5]
        for (int i = 0; i < right - left; i++){
            // 对于断开链接的技巧：作为中间数 3 会比较难处理，我们可以先将 3 节点保存下来，然后 2 -> 4， 3 -> 2， 1 -> 3
            ListNode removed = point.next;  // 将 3 记录起来，因为后续的 2 需要指向 4，那么指向 3 的链接的就断了
            point.next = point.next.next;   // 将 2 -> 4

            removed.next = pre.next;  // 3 -> 2
            pre.next = removed;       // 1 -> 3. 目前结果:[1,3,2,4,5]
        }
        return dummyHead.next;
    }
}
